package com.example.arithmeticleetcode.learnArithmetic2.greedy;

import java.util.*;

/**
 * @program: arithmetic-leetcode
 * @description: 背包 争取价值最大化
 * @author: FangZhen
 * @create: 2020-12-14 14:29
 **/
public class Knapsack {


    public static void main(String[] args) {
//        select("价值主导", (a1, a2) -> a2.value - a1.value);
//        System.out.println("---------------------------------------");
//        select("重量主导", (a1, a2) -> a1.weight - a2.weight);
//        System.out.println("----------------------------------------------------------");
//        select("价值密度主导", (a1, a2) -> Double.compare(a2.valueDensity, a1.valueDensity));
//        System.out.println("========================");
//        int[] values = {6, 3, 5, 4, 6};
//        int[] weights = {2, 2, 6, 5, 4};
//        int capacity = 10;
//        System.out.println(maxValue(values, weights, capacity));
//        System.out.println(maxValue2(values, weights, capacity));

        select2("价值主导", (a1, a2) -> a2.value - a1.value);
        System.out.println("---------------------------------------");
        select2("重量主导", (a1, a2) -> a1.weight - a2.weight);
        System.out.println("----------------------------------------------------------");
        select2("价值密度主导", (a1, a2) -> Double.compare(a2.valueDensity, a1.valueDensity));
        System.out.println("========================");

    }

    private static void select(String title, Comparator<Article> cmp) {
        Article[] articles = new Article[]{
                new Article(35, 10),
                new Article(30, 40),
                new Article(60, 30),
                new Article(50, 50),
                new Article(40, 35),
                new Article(10, 40),
                new Article(25, 30),
        };

        Arrays.sort(articles, cmp);
        List<Article> list = new ArrayList<>();
        int capacity = 150, weight = 0, value = 0;
        for (int i = 0; i < articles.length && weight < capacity; i++) {
            int newWeight = weight + articles[i].weight;
            if (newWeight <= capacity) {
                value += articles[i].value;
                weight = newWeight;
                list.add(articles[i]);
            }
        }
        System.out.println("【" + title + "】");
        System.out.println("最大重量：" + weight + ", 最大价值：" + value);
        System.out.println(list);
    }

    private static void select2(String title, Comparator<Article> cmp) {
        Article[] articles = new Article[]{
                new Article(2000, 1),
                new Article(2000, 1),
                new Article(4000, 1),
                new Article(4000, 1),
                new Article(5000, 1),
                new Article(5000, 1),
                new Article(6000, 1),
                new Article(6000, 1),
        };

        Arrays.sort(articles, cmp);
        List<Article> list = new ArrayList<>();
        int capacity = 10000, weight = 0, value = 0;
        for (int i = 0; i < articles.length && weight < capacity; i++) {
            int newWeight = weight + articles[i].weight;
            if (newWeight <= capacity) {
                value += articles[i].value;
                weight = newWeight;
                list.add(articles[i]);
            }
        }
        System.out.println("【" + title + "】");
        System.out.println("最大重量：" + weight + ", 最大价值：" + value);
        System.out.println(list);
    }

    /**
     * 一维数组实现
     *
     * @param values
     * @param weights
     * @param capacity
     * @return
     */
    public static int maxValue2(int[] values, int[] weights, int capacity) {
        if (values == null || values.length == 0) return 0;
        if (weights == null || weights.length == 0) return 0;
        if (values.length != weights.length || capacity <= 0) return 0;
        int[] dp = new int[capacity + 1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = capacity; j >= 1; j--) {
                if (j < weights[i - 1]) continue;
                dp[j] = Math.max(dp[j], values[i - 1] + dp[j - weights[i - 1]]);
            }
        }
        return dp[capacity];
    }

    /**
     * 二维数组实现
     *
     * @param values
     * @param weights
     * @param capacity
     * @return
     */
    public static int maxValue(int[] values, int[] weights, int capacity) {
        if (values == null || values.length == 0) return 0;
        if (weights == null || weights.length == 0) return 0;
        if (values.length != weights.length || capacity <= 0) return 0;
        int[][] dp = new int[values.length + 1][capacity + 1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < weights[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
                }
            }
        }
        return dp[values.length][capacity];
    }

    public static int countStudents(int[] students, int[] sandwiches) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int student : students) {
            map.put(student, map.getOrDefault(student, 0) + 1);
        }
        int count = sandwiches.length;
        for (int sandwich : sandwiches) {
            Integer integer = map.get(sandwich);
            if (integer == null || integer == 0) return count;
            map.put(sandwich, integer - 1);
        }
        return count;
    }

    public static int countStudents2(int[] students, int[] sandwiches) {
        if (students == null || students.length == 0) return 0;
        if (sandwiches == null || sandwiches.length == 0) return students.length;
        //  因为涉及到学生从队头移动到队尾，使用队列
        Queue<Integer> stu = new LinkedList<>();
        for (int student : students) {
            stu.offer(student);
        }
        for (int i = 0; i < sandwiches.length; i++) {
            // 队列为空，说明所有学生都满足了
            if (stu.isEmpty()) {
                return 0;
            }
            // 记录学生队列的长度，防止学生无限制转圈下去
            int size = stu.size();
            boolean like = false;
            for (int s = 0; s < size; s++) {
                int poll = stu.poll();
                if (poll != sandwiches[i]) {
                    // 学生移动到队尾
                    stu.offer(poll);
                } else {
                    // 顶层的三明治有人喜欢，停止遍历，继续判断下一块三明治（这跟拍卖似的^_^）
                    like = true;
                    break;
                }
            }
            if (!like) {
                // 顶层的三明治没有人喜欢，结束，返回不能满足的学生数
                return size;
            }
        }
        return stu.size();
    }

}
